Race car

Time: O(NLogN); Space: O(N); hard

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:

Input: target = 3

Output: 2

Explanation:

  • The shortest instruction sequence is “AA”.

  • Your position goes from 0->1->3.

Example 2:

Input: target = 6

Output: 5

Explanation:

  • The shortest instruction sequence is “AAARA”.

  • Your position goes from 0->1->3->7->7->6.

Constraint:

  • 1 <= target <= 10000

1. Dynamic Programming [O(NLogN), O(N)]

[1]:

class Solution1(object):
    """
    Time: :O(NLogN), N is the value of the target
    Space: O(N)
    """
    def racecar(self, target):
        dp = [0] * (target+1)
        for i in range(1, target+1):
            # 2^(k-1) <= i < 2^k
            k = i.bit_length()

            # case 1. drive exactly i at best
            #         seq(i) = A^k
            if i == 2**k-1:
                dp[i] = k
                continue

            # case 2. drive cross i at 2^k-1, and turn back to i
            #         seq(i) = A^k -> R -> seq(2^k-1 - i)
            dp[i] = k+1 + dp[2**k-1 - i]

            # case 3. drive less then 2^k-1, and turn back some distance,
            #         and turn back again to make the direction is the same
            #         seq(i) = shortest(seq(i), A^(k-1) -> R -> A^j -> R ->
            #                                   seq(i - (2^(k-1)-1) + (2^j-1)),
            #                  where 0 <= j < k-1)
            #         => dp[i] = min(dp[i], (k-1) + 1 + j + 1 +
            #                               dp[i - (2**(k-1)-1) + (2**j-1)])
            for j in range(k-1):
                dp[i] = min(dp[i], k+j+1 + dp[i - 2**(k-1) + 2**j])

        return dp[-1]

[2]:

s = Solution1()

target = 3
assert s.racecar(target) == 2